package com.demo.java.OD651_700.OD668;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【素数伴侣(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/148089728
 */
public class OdMain {
    // 预处理素数表，使用埃拉托斯特尼筛法
    private static boolean[] initPrimes(int max) {
        boolean[] isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= max; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }

    // 匈牙利算法寻找增广路径
    private static boolean find(int x, boolean[] vis, int[] match, boolean[][] graph, boolean[] isPrime) {
        for (int y = 0; y < vis.length; y++) {
            if (graph[x][y] && !vis[y]) {
                vis[y] = true;
                if (match[y] == -1 || find(match[y], vis, match, graph, isPrime)) {
                    match[y] = x;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i =  0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 最大可能的素数和是30000+30000=60000
        boolean[] isPrime = initPrimes(60000);

        // 分离奇数和偶数
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        for (int num : nums) {
            if (num % 2 == 1) {
                odds.add(num);
            } else {
                evens.add(num);
            }
        }

        int m = odds.size();
        int k = evens.size();
        boolean[][] graph = new boolean[m][k];

        // 构建二分图
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                if (isPrime[odds.get(i) + evens.get(j)]) {
                    graph[i][j] = true;
                }
            }
        }

        // 匈牙利算法求最大匹配
        int[] match = new int[k];
        Arrays.fill(match, -1);
        int result = 0;

        for (int i = 0; i < m; i++) {
            boolean[] vis = new boolean[k];
            if (find(i, vis, match, graph, isPrime)) {
                result++;
            }
        }

        System.out.println(result);
    }
}